package com.ai.zuochengyun.phase01.class01;

/**
 * MergeSort
 */
public class Code05_MergeSort {

    public static void main(String[] args) {
        int[] arr = new int[]{4, 2, 1, 3, 0, 6, 3, 9};
        mergeSort2(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    /**
     * 递归方法实现
     *
     * @param arr
     */
    public static void mergeSort1(int[] arr) {
        if (arr == null || arr.length == 1) {
            return;
        }
        // 让0~n-1范围内有序
        process(arr, 0, arr.length - 1);
    }

    /**
     * 时间复杂度 T(N)=2T(N/2)+O(N)  符合master公式 ==> O(N*logN)
     * O(N*logN) 比 O(N^2) 的好处在于：没有浪费比较结果
     *
     * @param arr
     * @param left
     * @param right
     */
    private static void process(int[] arr, int left, int right) {
        if (left == right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        // 让左边范围内有序
        process(arr, left, mid);
        // 让右边范围内有序
        process(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int size = right - left + 1;
        int[] help = new int[size];
        int p1 = left;
        int p2 = mid + 1;
        int index = 0;
        while (p1 <= mid && p2 <= right) {
            if (arr[p1] <= arr[p2]) {
                help[index++] = arr[p1++];
            } else {
                help[index++] = arr[p2++];
            }
        }
        while (p1 <= mid) {
            help[index++] = arr[p1++];
        }
        while (p2 <= right) {
            help[index++] = arr[p2++];
        }

        // 拷贝回原数组
        for (int i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }
    }

    /**
     * 迭代方法实现
     *
     * @param arr
     */
    public static void mergeSort2(int[] arr) {
        if (arr == null || arr.length == 1) {
            return;
        }

        int n = arr.length;
        int step = 1;
        while (step < n) {
            // 当前左组的第一个位置
            int left = 0;
            while (left < n) {
                // 先凑左组
                int mid = 0;
                // (n-1) - left + 1： 最后一个数到left位置的个数如果大于step个，表示能凑够左组
                if ((n - 1) - left + 1 > step) {
                    mid = left + step - 1;
                } else {
                    mid = n - 1;
                }
                // 不够凑右组了，直接跳出
                if (mid == n - 1) {
                    break;
                }

                // 再拼右边
                int right = 0;
                // (n-1) - (mid+1) + 1： 最后一个数到右组的第一个位置（即mid+1位置）的个数如果大于step个，表示能凑够右组
                if ((n - 1) - (mid + 1) + 1 > step) {
                    right = mid + 1 + step - 1;
                } else {
                    right = n - 1;
                }
                // 合并
                merge(arr, left, mid, right);
                // 右侧已经到末尾了，直接跳出
                if (right == n - 1) {
                    break;
                }
                left = right + 1;
            }
            if (step > n / 2) {
                break;
            }
            step = step * 2;
        }
    }
}
